// https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.player.switch&vd_source=d6fe65f095f01f05591e89d810720ccc&p=33
// 2024-10-25

public class P040_打家劫舍3_深度优先and动态规划 {

    // 树形街道
    public static void main(String[] args) {

        TreeNode node5 = new TreeNode(1,null,null);
        TreeNode node4 = new TreeNode(3,null,null);
        TreeNode node3 = new TreeNode(3,null,node5);
        TreeNode node2 = new TreeNode(2,null,node4);
        TreeNode node1 = new TreeNode(3,node2,node3);

        System.out.println(fun(node1));
    }

    private static int fun(TreeNode node1) {
        int[] i = dfs(node1);
        return Math.max(i[0],i[1]);//看偷和不偷根节点那个更大
    }

    private static int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0,0};//选中，和不选中。的最优解
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);

        int select = node.val + l[1] + r[1];//本节点选择
        int not_select = Math.max(l[0],r[0]); //本节点不选择

        return new int[] {select,not_select};
    }



    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
